package LeetCode.interview;

import java.util.LinkedList;

import edu.princeton.cs.algs4.Stack;
import util.LogUtils;

/*
 * 
 原题

 Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid. 
 The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not. 

 题目大意

 给定一个只包含(‘, ‘)’, ‘{‘, ‘}’, ‘[’ 和‘]’的字符串，验证它是否是有效的。括号必须配对，并且要以正确的顺序。 

 解题思路

 用一个栈来对输入的括号串进行处理，如果是左括号就入栈，如果是右括号就与栈顶元素看是否组成一对括号，组成就弹出，并且处理下一个输入的括号，如果不匹配就直接返回结果。 
 * @Date 2017-09-12 16：54
 */
public class _020_Valid_Parentheses {
	
	public boolean isValid(String s) {
		LinkedList<String> stack = new LinkedList();
		int index = 0;
		while (index < s.length()) {
			String ch = s.charAt(index++)+"";
			switch (ch) {
				case "(" :			
				case "[" :
				case "{" :
					stack.addFirst(ch);
					break;
				case ")" : {
					if (stack.isEmpty())	return false;
					String top = stack.getFirst();
					if (top.equals("(")) {
						stack.removeFirst();
					} 
					if (top.equals("[") || top.equals("{")) {
						return false;
					}
					break;
				}
				case "]" : {
					if (stack.isEmpty())	return false;
					String top = stack.getFirst();
					if (top.equals("[")) {
						stack.removeFirst();
					}
					if (top.equals("(") || top.equals("{"))	{
						return false;
					}
					break;
				}
				case "}" : {
					if (stack.isEmpty())	return false;
					String top = stack.getFirst();
					if (top.equals("{")) {
						stack.removeFirst();
					}
					if (top.equals("(") || top.equals("["))	{
						return false;
					}
					break;
				}
				default:
					return false;
			}
		}
		return stack.isEmpty();				//正确执行完成后，stack会清为空
	}

	public static void main(String[] args) {
		LogUtils.println("结果", new _020_Valid_Parentheses().isValid("[[["));
	}
}
